home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_2 / datastor < prev    next >
Internet Message Format  |  1995-03-31  |  6KB
  1. From noose.ecn.purdue.edu!samsung!sdd.hp.com!hp-pcd!hpcvra!jimd Sun Aug 12 09:11:46 EST 1990
  2. Article 951 of comp.sys.handhelds:
  3. Path: en.ecn.purdue.edu!noose.ecn.purdue.edu!samsung!sdd.hp.com!hp-pcd!hpcvra!jimd
  4. >From: jimd@hpcvra.CV.HP.COM (Jim Donnelly)
  5. Newsgroups: comp.sys.handhelds
  6. Subject: HP 48 Data Storage (long)
  7. Message-ID: <25590045@hpcvra.CV.HP.COM>
  8. Date: 12 Aug 90 02:37:23 GMT
  9. Organization: Hewlett-Packard Co., Corvallis, OR, USA
  10. Lines: 214
  11.  
  12.  
  13.     What follows is one of many possible solutions to a fairly
  14.     common data storage problem on the HP 48:
  15.  
  16.         "How do I store fields of variable length string
  17.          data in a compact, rapidly accessible manner that
  18.          does not require the overhead of storing strings
  19.          in lists?"
  20.  
  21.     I hope this will be of use to someone.  I'm sure that
  22.     many people have different "programming styles", so I'll
  23.     look forward to suggestions/code-packs/improvements/etc.
  24.  
  25.     -- Jim Donnelly
  26.     jimd@cv.hp.com
  27.  
  28.  
  29. ---------------------------------------------------------------------
  30.  
  31.  
  32.             Compact Data Storage
  33.  
  34.     A simple length-encoding technique can be put to use for a
  35.     free-format, very compact multi-field data storage system.
  36.     Tw
  37. o tiny programs, SUBNUM and STRCON are here to help the
  38.     process, and are listed near the end of this note.  At the
  39.     end of the note is a directory that may be downloaded into
  40.     the HP 48 that contains the examples.
  41.  
  42.     The principle is to store starting indices in the beginning
  43.     of a string that point to fields stored subsequently in the
  44.     string.  The indices are stored in field order, with an
  45.     additional index at the end to accommodate the last field.
  46.     There are several small points worth mentioning:
  47.  
  48.     1) Fields may be 0-length using this technique.
  49.     2) The execution time is uniform across all fields.
  50.     3) This technique saves about 4 bytes per field after
  51.        the first field, because the string prolog and length
  52.        are omitted for fields 2 -> n.
  53.  
  54.  
  55.     EXAMPLE:
  56.     --------
  57.  
  58.                      Indices  |          Fields
  59.           Character               |     1 11111111 12222222222
  60.           Position :   1  2  3  4 |567890 12345678 90123456789
  61.                   +--+--+--+--+------+--------+-----------+
  62.           String :    | 5|11|19|30|Field1| Field2 |  Field 3  |
  63.                       +--+--+--+--+------+--------+-----------+
  64.  
  65.     This is a string that contains 3 fields, and therefore 4
  66.     index entries.  The first field begins at character 5, the
  67.     second field begins at character 11, and the third field
  68.     begins at character 19. To keep the pattern consistent,
  69.     notice that the index for field 4 is 30, which is one more
  70.     than the length of the 29 character data string.
  71.  
  72.     To extract the second field, place the string on the stack,
  73.     use SUBNUM on character 2 to extract the starting position,
  74.     use SUBNUM on character 3 to extract the (ending position +1),
  75.     subtract 1 from the (ending position+1), then do a SUB to
  76.     get the field data.  NOTE: The index for field 1 is stored
  77.     as character code 5, NOT "5"!  To place the field index for
  78.     field 1 in the string, you would execute "data" 1 5 CHR REPL.
  79.  
  80.  
  81.     PROGRAM:
  82.     --------
  83.  
  84.     The following program accepts an encoded data string in
  85.     level 2 and a field number in level 1:
  86.  
  87.     DECODE     "data"  field#  -->  "field"
  88.  
  89.     <<  --> f
  90.       <<
  91.         DUP f SUBNUM        ; "data" start -->
  92.         OVER f 1 + SUBNUM        ; "data" start end+1 -->
  93.         1 -                ; "data" start end -->
  94.         SUB                ; "field" -->
  95.       >>
  96.     >>
  97.  
  98.  
  99.     DATA ENCODING
  100.     -------------
  101.  
  102.     The following program expects a series of 'n' strings on
  103.     the stack and encodes them into a data string suitable
  104.     for reading by the first example above.
  105.  
  106.     The programs SUBNUM and STRCON are used to assemble the
  107.     indices.
  108.  
  109.     ENCODE      field n  ...  field 1   n   -->  "data"
  110.  
  111.     << DUP 2 + DUP 1 - STRCON --> n  data
  112.       <<
  113.         1 n
  114.         FOR i
  115.           data i SUBNUM OVER SIZE    ; ... field index fieldsize
  116.           + data SWAP        ; ... field "data" index'
  117.           i 1 + i + SWAP CHR REPL    ; ... field "data"'
  118.           SWAP + 'data' STO        ; ...
  119.         NEXT
  120.         data            ; "data"
  121.           >>
  122.     >>
  123.  
  124.     In this example, four strings are encoded:
  125.  
  126.     Input:  5: "String"
  127.         4: "Str"
  128.         3: "STR"
  129.         2: "STRING"
  130.         1:         4
  131.  
  132.     Output: "xxxxxSTRINGSTRStrString"      (23 character string)
  133.     (The first five characters have codes 6, 12, 15, 18, and 24)
  134.  
  135.  
  136.  
  137.     VARIATION:
  138.     ----------
  139.  
  140.     The technique above has a practical limit of storing
  141.     up to 254 characters of data in a string.  To overcome
  142.     this, just allocate two bytes for each field position.
  143.     The code to extract the starting index for becomes a
  144.     little more busy.  In this case, the index is stored as
  145.     two characters in hex.
  146.  
  147.                   Indices  |          Fields
  148.        Character               | 11111 11111222 22222223333
  149.        Position :   12 34 56 78|901234 56789012 34567890123
  150.                    +--+--+--+--+------+--------+-----------+
  151.        String :    |09|0F|17|21|Field1| Field2 |  Field 3  |
  152.                    +--+--+--+--+------+--------+-----------+
  153.  
  154.        <<  --> f
  155.          <<
  156.         DUP f 2 * 1 -          ; "data" "data" indx1 -->
  157.         SUBNUM 16 *        ; "data" 16*start_left_byte  -->
  158.          OVER f 2 * SUBNUM +     ; "data" start
  159.         OVER f 2 * 1 + SUBNUM    ; "data" start end_left_byte -->
  160.         16 * 3PICK f 1 + 2 *
  161.         SUBNUM + 1 -        ; "data" start end -->
  162.         SUB            ; "field"  -->
  163.          >>
  164.        >>
  165.  
  166.  
  167.  
  168.     TWO VERY TINY HELPFUL PROGRAMS
  169.     ------------------------------
  170.  
  171.     SUBNUM        "string"  position  -->  code
  172.  
  173.     << DUP SUB NUM >>
  174.  
  175.  
  176.  
  177.     STRCON        code  count  -->  "repeated string"
  178.  
  179.     << -->  code count
  180.       << "" code CHR 'code' STO
  181.          1 count START code + NEXT
  182.           >>
  183.     >>
  184.  
  185.  
  186.     A DIRECTORY YOU CAN DOWNLOAD
  187.     ----------------------------
  188.  
  189.     This is a directory object.  Cut after the === to the end of
  190.     the file and download to your HP 48 using the ASCII transfer.
  191.  
  192. ========================================================================
  193. %%HP: T(3)A(D)F(.);
  194. DIR
  195.   DECODE
  196.     \<< \-> f
  197.       \<< DUP f
  198. SUBNUM OVER f 1 +
  199. SUBNUM 1 - SUB
  200.       \>>
  201.     \>>
  202.   ENCODE
  203.     \<< DUP 2 + DUP 1
  204. - STRCON \-> n data
  205.       \<< 1 n
  206.         FOR i data
  207. i SUBNUM OVER SIZE
  208. + data SWAP i 1 +
  209. SWAP CHR REPL SWAP
  210. + 'data' STO
  211.         NEXT data
  212.       \>>
  213.     \>>
  214.   STRCON
  215.     \<< \-> code count
  216.       \<< "" code CHR
  217. 'code' STO 1 count
  218.         START code
  219. +
  220.         NEXT
  221.       \>>
  222.     \>>
  223.   SUBNUM
  224.     \<< DUP SUB NUM
  225.     \>>
  226. END
  227.  
  228.  
  229.